// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func Longest(str1, str2 string) int {
	len1 := len(str1)
	len2 := len(str2)
	tab := make([][]int, len1+1)
	for i := range tab {
		tab[i] = make([]int, len2+1)
	}

	i, j := 0, 0
	for i = 0; i <= len1; i++ {
		for j = 0; j <= len2; j++ {
			if i == 0 || j == 0 {
				tab[i][j] = 0
			} else if str1[i-1] == str2[j-1] {
				tab[i][j] = tab[i-1][j-1] + 1
				if i < len1 {
					fmt.Printf("%c", str1[i])
					//移动到两个序列中的下一个字符
					i++
					j++
				}
			} else {
				tab[i][j] = max(tab[i-1][j], tab[i][j-1])
			}
		}
	}
	fmt.Println()
	return tab[len1][len2]
}

func max(more ...int) int {
	maxNum := more[0]
	for _, elem := range more {
		if maxNum < elem {
			maxNum = elem
		}
	}
	return maxNum
}

func main() {
	str1 := "TABTABTAB"
	str2 := "ATABTABTAB"
	fmt.Println(Longest(str1, str2))
}

//$ go run lcs.go
//ABTBTA
//1
